1. Field of the Invention
The present invention relates to a cryptographic method which provides a high level of data security, and more particularly, to a cryptographic method with elliptic curves.
2. Description of Related Art
Generating and verifying electronic signatures is one of the methods to authenticate data transmitted via a public digital network system or to identify a data sender, and privacy communication is one of the methods to transmit data to an intended receiver alone without leakage to a third party. These methods often exploit a public key cryptosystem (PKC), where an enciphering key is open to the public while a deciphering key is kept in secret to each user, or a common key which plays a role of both the enciphering and deciphering keys is generated from the data exchanged between the concerned users and kept in secret. Given that it is relatively easy to manage these keys, PKC has now become an essential technique when a user wishes to communicate with more than one users in secret.
A level of security for PKC often depends on a problem of finding a discrete logarithm (DLP) on a finite field. Assume q is a power of a prime number, GF(q) is a finite field such that the order of GF(q) is divisible by a large prime number, and an element g is a base point, then the DLP is as follows: Given an element y of GF(q), find an integer x such that y=g.sup.x, if such an integer x exists. Although it is easy to find y from g and x, it is a challenge to find x from y and g.
With referring to FIG. 1, how the DLP is applied to cryptography will be explained.
Here, let q=p.sup.1 where p is a prime number, GF(q)=GF(p), g be a primitive root of GF(p), t be an arbitrary positive integer satisfying 1.ltorsim.t.ltorsim.p-1, u be an arbitrary positive integer satisfying 1.ltorsim.u.ltorsim.p-1, .alpha. be a residue of g.sup.t modulo p(.alpha..ident.g.sup.t (mod p)), .beta. be a residue of g.sup.u modulo p(.beta..ident.g.sup.u (mod p)), and k be a residue of g to the tu-th power(k.ident.g.sup.tu (mod p)), then it is easy to find .alpha. with g, p, and t, but it is quite difficult to find t using g, p and .alpha.; likewise, it is easy to find .beta. with g, p and u, but it is quite difficult to find u using g, p and .beta..
Now in practice application where a user T wishes to send a message to a user U alone in secret, the users T and U respectively select t and u as secret keys to calculate .alpha. and .beta. with public data--p, GF(p), and g--which have been already provided to each user from the system provider. Then, they exchange .alpha. and .beta. to construct the common key k according to: ##EQU1##
More specifically, let p=11, g=2, t=4, u=8, then .alpha.=5 and .beta.=3, and thus we have k=4.
These days, data are transmitted in the form of bit sequences h.sub.1, h.sub.2, . . . , h.sub.i via digital public network system. This is because most of the systems employ digital hardware for enhancing transmission quality. Therefore, these bit sequences are enciphered and deciphered with k; these bit sequences may be enciphered by being multiplied by k, added to k, or ORed exclusively with k at the site of a data sender, and deciphered into the original data by an inverse process at the site of a receiver. Should a third party receive the enciphered data either intentionally or unintentionally, he will never be able to decipher them unless he finds g.sup.tu. A level of security can be enhanced when the user replaces his secret key regularly, for example, every six months. In addition, users have less possibilities to select the secret keys of the same number as p becomes larger.
The privacy communication applied with DLP is not limited to a pair communication. For example, two other users, a user V and a user W, respectively withholding secret keys c and d, can join the above-described communication by calculating and exchanging the common keys--g.sup.tu, g.sup.tv, g.sup.tw, g.sup.uv, g.sup.uw, and g.sup.vw with each other.
Also, the data may be transmitted through an intermediate user: the sender first transmits the enciphered data to the intermediate user by using a common key and then the intermediate user transmits them to the receiver with the acknowledgement of the receipt and transmission by using another common key. By doing so, the data transmission and receipt thereof can be documented.
The privacy communication is also employed in image data transmission, for example, in a subscription television service (STV) where deciphering equipments are provided to each subscriber, so that only those who have paid the charges can enjoy programs.
However, with every technical advancement in this field, the time required to solve DLP is getting shorter as is explained in "Cryptography: A Prime", Alan G. Konheim, John Wiely & Sons, Inc. To maintain the same level of security, the DLP on elliptic curves(EDLP), where an elliptic curve is used instead of the finite field, was proposed. The elliptic curve, such as one shown in FIG. 2, is an abelian manifold, or a projective algebraic curve with an irreducible and a non-singular genus 1 given by: EQU Y.sup.2 =X.sup.3 +a*X+b
where the characteristic of a finite field K is neither 2 nor 3, and a and b are elements of K.
Now, assume q is a power of a prime number, GF(q) is a finite field, E(GF(q)) is a group of elements of GF(q) on an elliptic curve E, and an element P of E(GF(q)) is a base point such that the order of P is divisible by a large prime number, then the EDLP is as follows: Given an element Q of E(GF(q)), find an integer x such that Q=xP, if such an integer x exists. Like the DLP, it is easy to find Q from x and P, but it is difficult to find x from Q and P.
A point P.sub.3 ', which is symmetric with respect to the x-axis to P.sub.3, is assigned by P.sub.1 +P.sub.2 on the elliptic curve, and P.sub.3 is an intersection of the elliptic curve and a straight line passing both P.sub.1 and P.sub.2 ; when P.sub.1 =P.sub.2, the straight line is a tangential line of the elliptic curve at P.sub.1. Hence, Q, or x-fold multiple of P, is defined by consecutively adding P a number of x times. Thus, ##EQU2## where the number of terms in the sum is x.
Therefore, the data can be enciphered and deciphered by a specific computation with P. Given that P is a two dimensional value consisting of x and y coordinates, (x, y), the sender and receiver must notify which of coordinates is used for the communication in advance. Of course only one of them may be used invariably, or both of them may be used together.
No solution such that confers a sub-exponential algorithm has been proposed to EDLP yet. Therefore, the privacy communication as secure as the one depending on the DLP could be realized by constructing a relatively small finite field which requires less amount of data and hence simplifies computation for constructing EDLP. This is preferable because the computation is generally carried out in processor chip cards(integrated circuits), or so-called smart cards, provided with the network system, and a capacity thereof and the ability of associated CPU are limited.
For this reason, EDLP had been widely applied to PKC for the singed or privacy communication until MOV reduction was proposed in 1991. In the MOV reduction, EDLP having P.epsilon.E(GF(q)) as the base point is reduced to DLP over an extensive GF(q.sup.r) when the order of P and q are relatively prime; particularly, DLP on the supersingular elliptic curve is reduced to an extensive at most GF(q.sup.6) of GF(q). [For further information, see "Reducing Elliptic Curve Logarithm to Logarithm in a Finite Field", A. Menezes, S. A. Vanstone and T. Okamoto, STOC 91.] As a result, EDLP constructed even with a supersingular elliptic curve of 97-bit long is no longer as secure as it had been thought.
However, against the attack by the MOV reduction, a variety of methods have been proposed for constructing irreducible EDLP by determining an adequate elliptic curve. Some of these methods are disclosed in "Non-supersingular Elliptic Curves for Public Key Cryptosystems", T. Beth and F. Schaefer, Eurocrypt '91, 1991, and U.S. patent application Ser. Nos. 07/904,944 filed Jun. 26, 1992, and 08/048,478, filed Apr. 16, 1993, of Miyaji et al., now U.S. Pat. Nos. 5,272,755 and 5,351,297 respectively.
Thanks to these newly proposed methods, irreducible EDLP with a small finite field is available to cryptography now. In the following, three typical applications of such cryptography will be explained.